计蒜客 贝壳找房户外拓展（中等）

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
主力强啊
考试时写分块没时间调试了
x轴扫描线+区间维护一次函数
线段树啊写啥分块。。
困难版要k-d tree，不会
重点在区间可以维护一次函数
顺序不需要管
因为合并就是从左到右的（我傻了）
一位网友跟我讲可以按y扫描线
但我不太会
（询问可能重叠但是插入不会）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=100008,mod=323232323;
int n,m,qn;
char ch;
int an,tmp;
struct node{
	int l,r,y,p,q;
}a[N];
inline bool cmpa(const node &a,const node &b)
{
	if(a.l!=b.l)	return a.l<b.l;
	return a.r<b.r;
}
bool vis[N];
int bn;
struct nodeq{
	int x,l,r,id;
}b[N];
inline bool cmpb(const nodeq &a,const nodeq &b)
{
	return a.x<b.x;
}
int ans[N],cnt;
priority_queue<PII,vector<PII>,greater<PII> > q;
struct node_tree{
	int p,q;
}tree[N<<2];
inline void pushup(int t)
{
	int lson=t<<1,rson=t<<1|1;
	tree[t].p=1ll*tree[lson].p*tree[rson].p%mod;
	tree[t].q=(1ll*tree[lson].q*tree[rson].p+tree[rson].q)%mod;
} 
inline void update(int t,int l,int r,int dest,int p,int q)
{
	if(l==dest&&r==dest){
		tree[t].p=p;
		tree[t].q=q;
		return;
	}
	int mid=(l+r)>>1;
	if(dest<=mid)	update(t<<1,l,mid,dest,p,q);
	else	update(t<<1|1,mid+1,r,dest,p,q);
	pushup(t);
	return;
}
inline void query(int t,int l,int r,int ll,int rr)
{
	if(ll<=l&&r<=rr){
		cnt=(1ll*cnt*tree[t].p+tree[t].q)%mod;
		return;
	}
	int mid=(l+r)>>1;
	if(ll<=mid)	query(t<<1,l,mid,ll,rr);
	if(mid<rr)	query(t<<1|1,mid+1,r,ll,rr);
	return;
}
int main()
{
	n=read();m=read();qn=read();
	for(int i=1;i<=m*4;++i){
		tree[i].p=1;
	}
	while(qn--){
		ch=getchar();
		while(ch<'A'||ch>'Z')	ch=getchar();
		if(ch=='I'){
			++an;
			a[an].l=read();
			a[an].r=read();
			a[an].y=read();
			a[an].p=read();
			a[an].q=read();
			vis[an]=1;
		}
		if(ch=='D'){
			tmp=read();
			vis[tmp]=0;
		}
		if(ch=='Q'){
			++bn;
			b[bn].x=read();
			b[bn].l=read();
			b[bn].r=read();
			b[bn].id=bn;
		}
	}
	tmp=an;an=0;
	for(int i=1;i<=tmp;++i){
		if(vis[i]){
			a[++an]=a[i];
		}
	}
	sort(a+1,a+an+1,cmpa);
	sort(b+1,b+bn+1,cmpb);
	tmp=1;
	for(int i=1;i<=bn;++i){
		while(a[tmp].l<=b[i].x&&tmp<=an){
			q.push(mp(a[tmp].r,tmp));
			update(1,1,m,a[tmp].y,a[tmp].p,a[tmp].q);
			++tmp;
		}
		while(!q.empty()&&q.top().first<b[i].x){
			update(1,1,m,a[q.top().second].y,1,0);
			q.pop();
		}
		cnt=0;
		query(1,1,m,b[i].l,b[i].r);
		ans[b[i].id]=cnt;
	}
	for(int i=1;i<=bn;++i){
		printf("%d\n",ans[i]);
	} 
	return 0;
}

分块终于过了
千万不要将0也搞到块里面（很麻烦
请这样写
be[i]=(i-1)/blk+1;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=100008,mod=323232323,BLK=330;
int n,m,qn,blk;
int be[N];
char ch;
int an,tmp;
struct node{
	int l,r,y,p,q;
}a[N];
inline bool cmpa(const node &a,const node &b)
{
	if(a.l!=b.l)	return a.l<b.l;
	return a.r<b.r;
}
bool vis[N];
int bn;
struct nodeq{
	int x,l,r,id;
}b[N];
inline bool cmpb(const nodeq &a,const nodeq &b)
{
	return a.x<b.x;
}
int ans[N];
LL cnt;
priority_queue<PII,vector<PII>,greater<PII> > q;
struct node_blk{
	LL p,q;
}c[N],block[BLK];
inline void update(int dest,int p,int q)
{
	c[dest].p=p;c[dest].q=q;
	int l=(be[dest]-1)*blk+1,r=min(m,be[dest]*blk);
	p=1;q=0;
	for(int i=l;i<=r;++i){
		p=1ll*p*c[i].p%mod;
		q=(1ll*q*c[i].p+c[i].q)%mod;
	}
	block[be[dest]].p=p;
	block[be[dest]].q=q;
}
inline void query(int l,int r)
{
	cnt=0;
	if(be[l]==be[r]){
		for(int i=l;i<=r;++i){
			cnt=(1ll*cnt*c[i].p+c[i].q)%mod;
		}
	}
	else{
		for(int i=l;i<=be[l]*blk;++i){
			cnt=(1ll*cnt*c[i].p+c[i].q)%mod;
		}
		for(int i=be[l]+1;i<be[r];++i){
			cnt=(1ll*cnt*block[i].p+block[i].q)%mod;
		}
		for(int i=(be[r]-1)*blk+1;i<=r;++i){
			cnt=(1ll*cnt*c[i].p+c[i].q)%mod;
		}
	}
}
int main()
{
	n=read();m=read();qn=read();
	blk=sqrt(m);
	for(int i=1;i<=m;++i){
		be[i]=(i-1)/blk+1;
		c[i].p=1;
	}
	for(int i=1;i<=m/blk+1;++i){//m/blk+1才是块数 
		block[i].p=1;
	}
	while(qn--){
		ch=getchar();
		while(ch<'A'||ch>'Z')	ch=getchar();
		if(ch=='I'){
			++an;
			a[an].l=read();
			a[an].r=read();
			a[an].y=read();
			a[an].p=read();
			a[an].q=read();
			vis[an]=1;
		}
		if(ch=='D'){
			tmp=read();
			vis[tmp]=0;
		}
		if(ch=='Q'){
			++bn;
			b[bn].x=read();
			b[bn].l=read();
			b[bn].r=read();
			b[bn].id=bn;
		}
	}
	tmp=an;an=0;
	for(int i=1;i<=tmp;++i){
		if(vis[i]){
			a[++an]=a[i];
		}
	}
	sort(a+1,a+an+1,cmpa);
	sort(b+1,b+bn+1,cmpb);
	tmp=1;
	for(int i=1;i<=bn;++i){
		while(a[tmp].l<=b[i].x&&tmp<=an){
			q.push(mp(a[tmp].r,tmp));
			update(a[tmp].y,a[tmp].p,a[tmp].q);
			++tmp;
		}
		while(!q.empty()&&q.top().first<b[i].x){
			update(a[q.top().second].y,1,0);
			q.pop();
		}
		query(b[i].l,b[i].r);
		ans[b[i].id]=cnt;
	}
	for(int i=1;i<=bn;++i){
		printf("%d\n",ans[i]);
	} 
	return 0;
}